0% completed
Problem Statement
Given a string s, representing the arithmetic expressions, evaluate the expression and return the resultant value.
Constraints:
- s contains digits, '+', '-', '(', ')', and ' '.
- '+' is used as addition operation but not as a unary operator. (i.e., "+2" and "+(1 + 3)" is invalid).
- '-' is used as a unary and subtraction operator both. (i.e., "-2" and "-(1 + 3)" is valid).
Note: You are not allowed to use the built-in function like eval() to evaluate the mathematical expression.
Examples
-
Example 1:
- Input:
"3 - (2 - 1) + 4" - Expected Output:
6 - Justification: The expression inside the parentheses
2 - 1evaluates to1. So the expression becomes3 - 1 + 4, which sums up to6.
- Input:
-
Example 2:
- Input:
"10 + (8 - (4 + 2)) - 1" - Expected Output:
11 - Justification: Inside the inner parentheses,
4 + 2equals6. The expression becomes10 + (8 - 6) - 1. Then8 - 6equals2, so it simplifies to10 + 2 - 1, which is11.
- Input:
-
Example 3:
- Input:
"5 + (3 - (2 + (8 - 5)) + 7) - (6 - 4)" - Expected Output:
8 - Justification: In the innermost parentheses,
8 - 5equals3. The expression becomes5 + (3 - (2 + 3) + 7) - (6 - 4). The next inner expression2 + 3equals5, so it becomes5 + (3 - 5 + 7) - 2. Simplifying further to5 + 5 - 2, we get10 - 2, which is8.
- Input:
Solution
To solve this problem, we utilize a stack-based approach to handle the precedence imposed by parentheses and to perform the calculations. This method is effective as stacks allow us to manage the order of operations and operands in a controlled manner.
Initially, we iterate through the expression, handling digits, operators, and parentheses separately. For digits, we construct numbers; for operators, we manage the current operation; and for parentheses, we use the stack to preserve the state of the calculation. When we encounter an open parenthesis, we push the current result and the sign onto the stack and reset them for the new inner expression. Upon encountering a closing parenthesis, we pop from the stack to restore the state and combine it with the current result. This method ensures that we maintain the correct order of operations and handle nested expressions effectively.
Step-by-Step Algorithm
-
Initialize Variables:
- Create a
resultvariable to store the cumulative result of the expression. - Define a
numbervariable to build numbers as they are read from the string. - Set a
signvariable to +1 or -1, indicating the current sign (positive or negative) for the number being processed. - Initialize a
stackto handle parentheses in the expression.
- Create a
-
Iterate Over the String:
- Loop through each character in the input string.
-
Process Each Character:
- If the character is a digit:
- Update
numberby multiplying the currentnumberby 10 and adding the new digit. This step builds multi-digit numbers from consecutive digits in the string.
- Update
- If the character is a '+' or '-':
- Apply the previous
signto the currentnumberand add it toresult. - Reset
numberto 0. - Update
signbased on whether the character is '+' (setsignto 1) or '-' (setsignto -1).
- Apply the previous
- If the character is an opening parenthesis '(':
- Push the current
resultandsignonto the stack. This step saves the current state before processing the expression inside the parentheses. - Reset
resultto 0 andsignto 1 to start calculating the expression inside the parentheses.
- Push the current
- If the character is a closing parenthesis ')':
- First, add the current
numbertoresultafter applying the currentsign. - Then, the expression inside the parentheses is complete. Pop the last
signfrom the stack and multiply it with the currentresult. - Pop the last saved
resultfrom the stack and add it to the currentresult. - Reset
numberto 0.
- First, add the current
- If the character is a digit:
-
Final Calculation:
- After the loop, there might be a number that hasn't been added to the
result. Add this number toresultafter applying the lastsign.
- After the loop, there might be a number that hasn't been added to the
-
Return Result:
- Return the final
result, which is the evaluation of the entire arithmetic expression.
- Return the final
5. Algorithm Walkthrough
Let's use the input "5 + (3 - (2 + (8 - 5)) + 7) - (6 - 4)":
-
Initialize Variables:
result = 0,number = 0,sign = 1,stack = [].
-
Process Each Character:
- '5':
number = 5. - '+':
result = 0 + (5 * 1) = 5,number = 0,sign = 1,stack = []. - '(': push
result (5)andsign (1)tostack,stack = [5, 1], resetresult = 0andsign = 1. - '3':
number = 3. - '-':
result = 0 + (3 * 1) = 3,number = 0,sign = -1,stack = [5, 1]. - '(': push
result (3)andsign (-1)tostack,stack = [5, 1, 3, -1], resetresult = 0andsign = 1. - '2':
number = 2. - '+':
result = 0 + (2 * 1) = 2,number = 0,sign = 1,stack = [5, 1, 3, -1]. - '(': push
result (2)andsign (1)tostack,stack = [5, 1, 3, -1, 2, 1], resetresult = 0andsign = 1. - '8':
number = 8. - '-':
result = 0 + (8 * 1) = 8,number = 0,sign = -1,stack = [5, 1, 3, -1, 2, 1]. - '5':
number = 5. - ')':
result = 8 + (5 * -1) = 3,result *= stack.pop() (1) = 3,result += stack.pop() (2) = 5,number = 0,stack = [5, 1, 3, -1]. - ')':
result *= stack.pop() (-1) = -5,result += stack.pop() (3) = -2, number = 0,stack = [5, 1]``. - '+':
sign = 1. - '7':
number = 7. - ')':
result = -2 + (7 * 1) = 5,result *= stack.pop() (1) = 5,result += stack.pop() (5) = 10,number = 0,stack = []. - '-':
sign = -1. - '(': push
result (10)andsign (-1)tostack,stack = [10, -1], resetresult = 0andsign = 1. - '6':
number = 6. - '-':
result = 0 + (6 * 1) = 6,number = 0,sign = -1, . - '4':
number = 4. - ')':
result = 6 + (4 * -1) = 2,result *= stack.pop() (-1) = -2,result += stack.pop() (10) = 8,number = 0,stack = []. - Final Calculation: The final
resultafter the loop is8.
- '5':
-
Return Result:
- The final
resultis8.
- The final
Code
Complexity Analysis
- Time Complexity: O(n), where
nis the length of the string. This is because each character in the string is processed exactly once. - Space Complexity: O(n), in the worst case, due to the stack used to handle parentheses. In the worst case, the stack's size is proportional to the number of parentheses, which can be as large as the length of the string.
On this page
Problem Statement
Examples
Solution
Step-by-Step Algorithm
- Algorithm Walkthrough
Code
Complexity Analysis